"""
作者：l00
链接：https://leetcode.cn/problems/check-if-dfs-strings-are-palindromes/solutions/2961895/xiang-jie-ha-xi-huo-manacher-by-l00-td0r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
from typing import List

base = 131
mod = 1_000_000_007
book = {ch: i for i, ch in enumerate("abcdefghijklmnopqrstuvwxyz", 1)}

products = []
mul = 1
for i in range(100_001):
    products.append(mul)
    mul = mul * base % mod


class Solution:
    def findAnswer(self, parent: List[int], s: str) -> List[bool]:
        n = len(parent)
        g = [[] for _ in range(n)]
        for ch, pa in enumerate(parent[1:], 1):
            g[pa].append(ch)
        ans = [True] * n

        def dfs(root: int):
            child = g[root]
            curPos = curNev = curLength = 0
            for ch in child:
                pos, nev, length = dfs(ch)
                curPos = (curPos + pos * products[curLength]) % mod
                curNev = (nev + curNev * products[length]) % mod
                curLength += length
            curPos = (curPos + book[s[root]] * products[curLength + 1]) % mod
            curNev = ((book[s[root]] + curNev) * products[1]) % mod
            ans[root] = curPos == curNev
            return curPos, curNev, curLength + 1

        dfs(0)
        return ans
